package study.datastructure.tree.leetcode;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2025-02-01 15:07
 */

import study.datastructure.tree.TreeNode;

import java.util.*;

/**
 * 2025/2/1,
 */


public class s1 {


    /**
     * 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。
     * 这条路径可能经过也可能不经过根节点 root 。
     * <p>
     * <p>
     * 直径为  左右子树深度和
     * 递归
     * 1
     * 2
     * 4
     * 5
     * <p>
     * 3
     * <p>
     * 二叉树直径 为 ： (L + R)
     * 1[(2)|(1)] + 1
     * 2(2)          3(1)
     * 0    0
     * 4(1)   5(1)
     * 0    0  0    0
     *
     * @param root
     * @return
     */
    private int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);

        return maxDiameter;
    }

    private int maxDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftDepth = maxDepth(node.left);
        int rightDepth = maxDepth(node.right);

        maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);

        return Math.max(leftDepth, rightDepth) + 1;

    }


    /**
     * 108. 将有序数组转换为二叉搜索树
     * 简单
     * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵
     * 平衡
     * 二叉搜索树。
     * <p>
     * <p>
     * [-10,-3,0,5,9]
     * 0
     * -10 -3    5  9
     * <p>
     * -10       5
     * -3        9
     * <p>
     * <p>
     * 递归分治
     *
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return bulidBST(nums, 0, nums.length - 1);
    }


    private TreeNode bulidBST(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        int mid = (left + right) / 2;

        TreeNode root = new TreeNode(nums[mid]);

        root.left = bulidBST(nums, left, mid - 1);
        root.right = bulidBST(nums, mid + 1, right);

        return root;


    }

    /**
     * 二叉树的层序遍历
     * <p>
     * 3
     * 9        20
     * 15      7
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);

                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            result.add(currentLevel);
        }
        return result;

    }


    /**
     * <盛最多水的容器></盛最多水的容器>
     * <p>
     * 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
     * <p>
     * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
     *
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;

        while (left < right) {
            // 计算面积
            maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left));
            // 移动指针
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;

    }

    /**
     * 二叉树 转 链表
     * <p>
     * 1
     * / \
     * 2   5
     * / \   \
     * 3   4   6
     * <p>
     * //将 1 的左子树插入到右子树的地方
     * 1
     * \
     * 2         5
     * / \         \
     * 3   4         6
     * //将原来的右子树接到左子树的最右边节点
     * 1
     * \
     * 2
     * / \
     * 3   4
     * \
     * 5
     * \
     * 6
     * <p>
     * //将 2 的左子树插入到右子树的地方
     * 1
     * \
     * 2
     * \
     * 3       4
     * \
     * 5
     * \
     * 6
     * <p>
     * //将原来的右子树接到左子树的最右边节点
     * 1
     * \
     * 2
     * \
     * 3
     * \
     * 4
     * \
     * 5
     * \
     * 6
     * <p>
     * ......
     *
     * @param root
     */
    public void flatten(TreeNode root) {
        if (root == null) return;

        while (root != null) {
            if (root.left == null) {
                root = root.right;
            } else {
                // 找到左子树最右边
                TreeNode pre = root.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                // 将左子树插入到右子树的地方
                pre.right = root.right;
                // 将原来的右子树接到左子树的最右边节点
                root.right = root.left;
                root.left = null;

                root = root.right;
            }
        }

    }


    /**
     * 前序 和中序构建二叉树
     * <p>
     * 前序遍历：第一个元素是根节点。
     * <p>
     * 中序遍历：根节点将数组分为左子树和右子树。
     * <p>
     * 递归构建：
     * <p>
     * 使用前序遍历确定根节点。
     * <p>
     * 在中序遍历中找到根节点的位置，划分左子树和右子树。
     * <p>
     * 递归构建左子树和右子树。
     *
     * @param preorder
     * @param inorder
     * @return
     */

    private int preIndex = 0;
    private Map<Integer, Integer> inMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            inMap.put(inorder[i], i);
        }
        return buildTree(preorder, 0, inorder.length - 1);
    }

    private TreeNode buildTree(int[] preorder, int left, int right) {
        if (left > right) {
            return null;
        }

        int rootVal = preorder[preIndex++];
        TreeNode root = new TreeNode(rootVal);
        Integer index = inMap.get(rootVal);

        root.left = buildTree(preorder, left,  index- 1);
        root.right = buildTree(preorder,index+1,right);
        return root;
    }

    /**
     * 二叉树的中序遍历
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inorder(root,list);
        return list;
    }
    private void inorder(TreeNode root,List<Integer> list){
        if (root == null) return;
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }
}
